Data Structures and Algorithms [html]

Aho A.V.,HopcroftJ.E.,Ullman J.D.Data structures and algorithms(AW,1985)(ISBN 0201000237)(600dpi)(440p) ......Page 3
Copyright iv ......Page 4
Preface vi ......Page 5
Contents viii ......Page 8
1.1 From Problems to Programs 1 ......Page 12
1.2 Abstract Data Types 10 ......Page 21
1.3 Data Types, Data Structures, and Abstract Data Types 13 ......Page 24
1.4 The Running Time of a Program 16 ......Page 27
1.5 Calculating the Running Time of a Program 21 ......Page 32
1.6 Good Programming Practice 27 ......Page 38
1.7 Super Pascal 29 ......Page 40
2.1 The Data Type “List” 37 ......Page 48
2.2 Implementation of Lists 40 ......Page 51
2.3 Stacks 53 ......Page 64
2.4 Queues 56 ......Page 67
2.5 Mappings 61 ......Page 72
2.6 Stacks and Recursive Procedures 64 ......Page 75
3.1 Basic Terminology 75 ......Page 86
3.2 The ADT TREE 82 ......Page 93
3.3 Implementations of Trees 84 ......Page 95
3.4 Binary Trees 93 ......Page 104
4.1 Introduction to Sets 107 ......Page 118
4.2 An ADT with Union, Intersection, and Difference 109 ......Page 120
4.3 A Bit-Vector Implementation of Sets 112 ......Page 123
4.4 A Linked-List Implementation of Sets 115 ......Page 126
4.5 The Dictionary 117 ......Page 128
4.6 Simple Dictionary Implementations 119 ......Page 130
4.7 The Hash Table Data Structure 122 ......Page 133
4.8 Estimating the Efficiency of Hash Functions 129 ......Page 140
4.10 Priority Queues 135 ......Page 146
4.11 Implementations of Priority Queues 138 ......Page 149
4.12 Some Complex Set Structures 145 ......Page 156
5.1 Binary Search Trees 155 ......Page 166
5.2 Time Analysis of Binary Search Tree Operations 160 ......Page 171
5.3 Tries 163 ......Page 174
5.4 Balanced Tree Implementations of Sets 169 ......Page 180
5.5 Sets with the MERGE and FIND Operations 180 ......Page 191
5.6 An ADT with MERGE and SPLIT 189 ......Page 200
6.1 Basic Definitions 198 ......Page 209
6.2 Representations for Directed Graphs 199 ......Page 210
6.3 The Single-Source Shortest Paths Problem 203 ......Page 214
6.4 The All-Pairs Shortest Path Problem 208 ......Page 219
6.5 Traversals of Directed Graphs 215 ......Page 226
6.6 Directed Acyclic Graphs 219 ......Page 230
6.7 Strong Components 222 ......Page 233
7.1 Definitions 230 ......Page 241
7.2 Minimum-Cost Spanning Trees 233 ......Page 244
7.3 Traversals 239 ......Page 250
7.4 Articulation Points and Biconnected Components 244 ......Page 255
7.5 Graph Matching 246 ......Page 257
8.1 The Internal Sorting Model 253 ......Page 264
8.2 Some Simple Sorting Schemes 254 ......Page 265
8.3 Quicksort 260 ......Page 271
8.4 Heapsort 271 ......Page 282
8.5 Bin Sorting 274 ......Page 285
8.6 A Lower Bound for Sorting by Comparisons 282 ......Page 293
8.7 Order Statistics 286 ......Page 297
9.1 Efficiency of Algorithms 293 ......Page 304
9.2 Analysis of Recursive Programs 294 ......Page 305
9.3 Solving Recurrence Equations 296 ......Page 307
9.4 A General Solution for a Large Class of Recurrences 298 ......Page 309
10.1 Divide-and-Conquer Algorithms 306 ......Page 317
10.2 Dynamic Programming 311 ......Page 322
10.3 Greedy Algorithms 321 ......Page 332
10.4 Backtracking 324 ......Page 335
10.5 Local Search Algorithms 336 ......Page 347
11.1 A Model of External Computation 347 ......Page 358
11.2 External Sorting 349 ......Page 360
11.3 Storing Information in Files 361 ......Page 372
11.4 External Search Trees 368 ......Page 379
12.1 The Issues in Memory Management 378 ......Page 389
12.2 Managing Equal-Sized Blocks 382 ......Page 393
12.3 Garbage Collection Algorithms for Equal-Sized Blocks 384 ......Page 395
12.4 Storage Allocation for Objects with Mixed Sizes 392 ......Page 403
12.5 Buddy Systems 400 ......Page 411
12.6 Storage Compaction 404 ......Page 415
Bibliography 411 ......Page 422
Index 419 ......Page 430
cover......Page 1